Masala #0748

Xotira 16 MB Vaqt 2500 ms Qiyinchiligi 65 %
14

  

Prefiks funksiya

Dasturlash musobaqasi bilan shug’ullanib yurgan barchaga Prefiks funksiya nima ekanligi ma’lum bo’lsa kerak. Agar bilmasangiz Prefiks funksiya haqida https://e-maxx.ru/algo/prefix_function havoladan o’rganib olishingiz mumkin.

Keling endi asosiy masalaga o’tamiz!

\(S\) to’plam \(m\) ta harfli alifbodan tuzilgan uzunligi \(n\) ga teng bo’lgan barcha satrlar to’plami.

\(F(s)\) funksiyasi \(\text{prefix\_function}(s)\) dan olingan to’plamning eng katta qiymati bo’lsin.

Sizning vazifangiz \(\sum_{s∈S}F(s)\) ni \(X\) ga bo’lgandagi qoldiqni hisoblashdan iborat.


Kiruvchi ma'lumotlar:

Kirish faylining yagona satrida uchta butun son, \(n (1 \le n \le 22)\), \(m (1 \le m \le 10^9)\) va \(X (1 \le X \le 10^9)\) sonlari kiritiladi.


Chiquvchi ma'lumotlar:

Chiqish faylida yagona butun son,   \(\sum_{s∈S}F(s)\) ni \(X\) ga bo’lgandagi qoldiqni chop eting!


Misollar
# input.txt output.txt
1
3 2 1000
8
Izoh:
  1. F(aaa) = 2
  2. F(aab) = 1
  3. F(aba) = 1
  4. F(abb) = 0
  5. F(baa) = 0
  6. F(bab) = 1
  7. F(bba) = 1
  8. F(bbb) = 2
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin